Problem statement: zenit14skd

Samci ondatry Maroško a Lukáš odjakživa zdieľali klietku s pekným výbehom. Ich vzájomné vzťahy sa ale naštrbili po nedávnom nepríjemnom incidente, plnom vzájomného obviňovania sa z toho, kto zjedol viac krmiva. Keďže nahnevané ondatry nepôsobia na návštevníkov lákavo, rozhodlo sa vedenie, že klietku predelí kameňmi na dve polovice a pohašterené strany konfliktu takto izoluje.

Výbeh vnútri pozostáva z trávičky, močiara, náhodne rozmiestnených kameňov a dvoch skrýš. Vedenie záhrady chce pomocou už rozmiestnených a nejakých novopridaných kameňov vybudovať bariéru. Táto bariéra musí byť kolmá na stenu klietky, cez ktorú sa pozerajú návštevníci. Zároveň treba docieliť, aby boli skrýše na rôznych stranách bariéry. Napíšte program, ktorý prečíta situáciu a zistí minimálny potrebný počet kameňov, ktoré treba pridať.

Formát vstupu

Na prvom riadku vstupu sú rozmery výbehu \(R\) a \(S\). Obe tieto čísla sú aspoň 3 a najviac 50. Na ďalších \(R\) riadkoch je na každom \(S\) znakov. Tieto znaky sú . (bodka, označuje trávu alebo močiar), # (označuje kameň) alebo X (označuje skrýšu). Skrýše sú na plániku práve dve a nevyskytnú sa v rovnakom ani v susedných stĺpcoch.

Formát výstupu

Na výstup vypíšte jedno číslo: minimálny počet kameňov, ktoré treba pridať na oddelenie dvoch znepriatelených ondatier. Na docielenie tohto stavu musí niektorý stĺpec pozostávať len z kameňov. Teritóriá nemusia byť rovnako veľké. Jedinou podmienkou je, aby boli skrýše na rôznych stranách tejto bariéry.

Príklady

Input:

4 5
.X#.#
.#...
..#.X
.....

Output:

2

Najvhodnejší je tretí stĺpec. Vzhľadom k polohe skrýš pripadá do úvahy ešte štvrtý stĺpec. Tam by sme ale potrebovali až 4 nové kamene.

Input:

5 5
X..#.
#.X##
##.#.
#....
...##

Output:

4

Tu nemáme na výber a musíme stavať bariéru cez druhý stĺpec, ak chceme oddeliť skrýše.

Input:

3 3
X##
.#.
.#X

Output:

0

Tu sú skrýše zhodou okolností už oddelené.

Input:

4 4
X#..
##..
..##
..#X

Output:

2

Tu sa síce zo skrýše do skrýše nevieme dostať, ale úloha požaduje jeden celý stĺpec z kameňov.